package com.sicheng.lc.周赛.分类.图论.拓扑排序;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/19 17:19
 */
public class 课程表II {
    //https://leetcode.cn/problems/course-schedule-ii/
    static ArrayDeque<Integer> deque = new ArrayDeque<>(1000);
    static int[] empty = {};

    {
        deque.clear();
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] degree = new int[numCourses];
        ArrayList<Integer>[] g = new ArrayList[numCourses];
        Arrays.setAll(g, k -> new ArrayList<>(15));

        for (int[] prerequisite : prerequisites) {
            g[prerequisite[1]].add(prerequisite[0]);
            degree[prerequisite[0]]++;
        }

        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0)
                deque.offer(i);
        }

        int[] res = new int[numCourses];
        int index = 0;
        int cnt = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            cnt += size;
            for (int i = 0; i < size; i++) {
                int x = deque.poll();
                res[index++] = x;
                for (int y : g[x]) {
                    degree[y]--;
                    if (degree[y] == 0)
                        deque.offer(y);
                }
            }
        }

        if (cnt < numCourses)
            return empty;
        return res;

    }
}
